package com.easy.carl.algorithm.tree;

import com.easy.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PathSum113 {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        //结果
        List<List<Integer>> res = new ArrayList<>();
        //路径
        List<Integer> path= new ArrayList<>();
        //总和
        int sum=0;
        if (root==null){
            return res;
        }
        //注意：第一次调用是，path和sum需要 记录下来
        sum+= root.val;
        path.add(root.val);
        help(root,sum,targetSum,res,path);
        return res;
    }

    public void help(TreeNode cur,int sum,int targetSum,List<List<Integer>> res,List<Integer> path) {
        //递归退出条件 叶子节点时退出
        if (cur.left == null && cur.right == null) {
            //System.out.println( Arrays.toString(path.toArray()));
            //和与目标值相等，记录路径
            if (sum == targetSum) {
                //注意，需要new 一个数组，存放path,否则会出现引用了同一个变量，回溯时list内容被删除
                res.add(new ArrayList<>(path));
            }
            return;
        }
        //左节点不为空 回溯
        if (cur.left != null) {
            //记录和
            sum += cur.left.val;
            //记录path
            path.add(cur.left.val);
            help(cur.left, sum, targetSum, res, path);
            sum -= cur.left.val;
            path.remove(path.size() - 1);
        }

        if (cur.right != null) {
            sum += cur.right.val;
            path.add(cur.right.val);
            help(cur.right, sum, targetSum, res, path);
            sum -= cur.right.val;
            path.remove(path.size() - 1);
        }
    }
}
